In relational data bases, it is a common practice to provide an index of a relational data base table in which the index is structured in levels and wherein each row of the table is identified by a respective row identifier (RID). The index can be defined by an ordered list of columns of the table and a concatenation of the list of columns, in a binary number, can serve as a key for the index. The index points to the respective rows of the table by the row identifiers. The index can be used to respond to a query defining a request to access a subset of the rows of the table. Values of some of the columns can be restricted, depending upon the query, to certain ranges and each of the ranges can consist of an ordered list of subranges which have upper and lower bounds.
Such indexes are used in many file systems and data base management systems in order to expedite access to the data contained therein.
Having indexes involves a trade-off, on the one hand, between the effort, disk space and time invested in the maintenance of indexes during update operations and, on the other hand, the effort and time spared when these indexes facilitate in finding relevant data and ignoring irrelevant data.